package com.datastructure.test.numberofdatainarray;

public class NumberOfDataInArray {
    int number = 0;
    public static void main(String[] args) {
        int[] data = {1,3,4,5};
        NumberOfDataInArray numberOfDataInArray = new NumberOfDataInArray();
        numberOfDataInArray.GetNumberOfK(data,6);
    }

    public int GetNumberOfK(int [] array , int k) {
        int length = array.length;
        getNumberOfK(array,0,length-1,k);
        return number;
    }

    private void getNumberOfK(int[] array, int left, int right, int target) {
        if(left>right){
            return;
        }
        int mid = (left+right)/2;
        int midValue = array[mid];
        if(midValue>target){
            getNumberOfK(array,left,mid-1,target);
        } else if(midValue<target){
            getNumberOfK(array,mid+1,right,target);
        } else {
            int temp = mid-1;
            while (temp >= 0 && array[temp] == midValue) {
                number++;
                temp--;
            }
            number++;
            temp=mid+1;
            while (temp <= array.length - 1 && array[temp] == midValue) {
                number++;
                temp++;
            }
        }
    }
}
